The present invention relates to a method for multi-step filtering a spatial object in a spatial database system; and, more particulary, to a method for multi-step refiltering a candidate object, which is filtered by minimum bounding rectangle (MBR), by employing a minimum maximum point (MMP) filter to improve a performance of spatial query processing performed in filtering and refinement steps.
A spatial database system has been generally used for a geographic information system (GIS) involved with managements of resources and facilities, e.g., territory, resources, electricity, telecommunication facility. The GIS has a plurality of data composed of spatial data and non-spatial data, and it consists essentially of millions of spatial objects. One of spatial objects includes geometrical characteristics of an object. The spatial characteristics consist essentially of simple figures, which are made up of points, lines, rectangles, polygons, and complex figures composed of these simple figures. The spatial object having these spatial characteristics is filtered and refined in association with requiry for spatial query during the spatial query processing. The spatial object is managed by a spatial index method, and spatial query processing is processed by using information of spatial index. However, the spatial object which the spatial index should manage is very irregular, and generally consists essentially of a plurality of points, so that the spatial object can not be used rawly as a key of the spatial index.
Therefore, as shown in FIG. 1, a conventional spatial query processing is achieved as follows: at step 10, a minimum bounding rectangle (Minimum Bounding Rectangle:MBR) is extracted in regard to a spatial object; at step 11, a spatial index is constructed by using the Minimum Bounding Rectangle of object extracted at step 10 as a key of the spatial index; at step 12, a spatial query is required by a user in regard to a spatial index key constructed at step 11; at step 13, a candidate object satisfactory to the spatial query is selected by comparing the minimum bounding rectangle (MBR) of a domain object given from the spatial query required at step 12 with the Minimum Bounding Rectangle of the spatial object constructed at step 11; at step 14, it is decided whether a candidate object is selected or not at step 13; at step 14, if a candidate object satisfactory to the spatial query is not selected at step 13, another object is filter-processed while comparing the Minimum Bounding Rectangle of the domain object on demand of the spatial query at step 12 with the Minimum Bounding Rectangle of the non-filter-processed spatial object among the spatial object constructed at step 11, on the other hand, if the candidate object is selected at step 13, at step 15 the object is refinement-processed by comparing a real shape of the selected candidate object with real shape of the domain object given at the spatial query at step 12; at step 16, it is decided whether the object matches the query condition or not; at step 16, if the object does not match the query condition, it goes back to step 13 and steps 13 and 15 are executed repeatedly; and, if the object matches the query, at step 17 it is contained in the satisfied object set.
However, because a filtering ratio of the Minimum Bounding Rectangle at the spatial query processing is low, there may be a problem in that lots of data should be processed at the refinement step at which it takes much time to operate the complex object.
To solve the problem, the method of multi-step filtering is provided, in which the candidate object filtered by using the Minimum Bounding Rectangle is refiltered by using various spatial filters whose ratio is higher than that of the Minimum Bounding Rectangular.
Accordingly, there have been provided various spatial filters surrounding an object, such as a rotated minimum bounding rectangle (RMBR), a minimum bounding circle (MBC), a minimum bounding ellipse (MBE), a minimum bounding convexhull, a minimum bounding n-corner (n-C) which consists of n points, maximum enclosed rectangle (MER) and a maximum enclosed line (MEL) which is the maximum value on x and y axises of the object. However, there is a problem in that these various filters can be generated only in regard to a areal object. Not only the processing of the areal object but also the processing of a linear object is indispensable in spatial database, so the filter considering the linear object and the areal object is minimum maximum point (MMP) filter which exists on the border line of the spatial object and consists of two or four points which have the minimum or the maximum value on x/y axis. This Minimum Maximum Point filter has the low consumption cost for generating or managing the filter, has the small memory space for storage, and has the characteristics that it can be applied not only to the areal object but also to the linear object. However, the method of milti-step filtering by utilizing Minimum Maximum Point filter can be applied to each well-known spatial operator used at the spatial database system is not provided yet.
It is, therefore, a primary object of the invention to provide a method for multi-step filtering by utilizing minimum maximum point (MMP) filter in a spatial data base system.
In accordance with one aspect of the present invention, there is provided a method of multi-step filtering by utilizing MMP filter in the spatial database system in order to improve performance of spatial query processing by refiltering candidate objects, which are filtered by using a minimum bounding rectangles (MBRs) surrounding spatial objects during the filtering step at spatial query processing by filtering and refinement steps in spatial database system, by using spatial filter, i.e., MMP filter.